class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // dp[i][j] 表示 [0, i - 1] 与 [0, j - 1] 的最长公共子序列长度
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                // 当前字母相等，那就在[0, i - 2] 与 [0, j - 2] 的最长公共子序列长度 的 基础上+1，也就是dp[i - 1][j - 1] + 1
                if(text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                // 如果不相等，比如abc，
                //                ace，
                // 遍历到c和e的时候，那么这个时候有两种情况
                // 1. 看abc和ac的最长公共子序列长度，dp[i][j - 1]
                // 2. 看ab和ace的最长公共子序列长度，dp[i - 1][j]
                // 二者取最大值
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
};